from typing import *
from math import inf


class Solution:
    def maxScore(self, a: List[int], b: List[int]) -> int:
        m, n = len(a), len(b)
        dp = [[-inf] * n for _ in range(m)]
        dp[0][0] = a[0] * b[0]
        for j in range(1, n):
            dp[0][j] = max(a[0] * b[j], dp[0][j - 1])
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i][j - 1], a[i] * b[j] + dp[i - 1][j - 1])
        return dp[3][n - 1]


so = Solution()
print(so.maxScore(a=[3, 2, 5, 6], b=[2, -6, 4, -5, -3, 2, -7]))
